package Array.easy;


import java.util.Arrays;
import java.util.HashMap;

/**
 * 1. 问题描述
 *      给你一个非负整数数组 nums 。如果存在一个数 x ，使得 nums 中恰好有x元素大于或者等于 x ，
 *      那么就称nums是一个特殊数组 ，而x是该数组的特征值 。
 *      注意：x不必是nums的中的元素。
 *      如果数组nums是一个特殊数组 ，请返回它的特征值x 。否则，返回-1可以证明的是，如果nums是特
 *      殊数组，那么其特征值x是唯一的
 *
 * 2. 算法分析
 *      1. 暴力法     时间复杂度为O(n^2)
 *      2. 排序+二分  时间复杂度为O(nlogn)
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 特殊数组的特征值 {
    // 暴力法
    public int specialArray1(int[] nums) {
        int n = nums.length;
        for(int x = 1; x <= n; x++) { // 扫描n种可能性
            int count = 0; // 记录数组中满足条件的元素个数
            for(int y : nums) {
                if(y >= x) {
                    count++;
                }
            }
            if(x == count) {
                return x;
            }
        }
        return -1;
    }


    // 优化
    // 二分法
    public static int specialArray2(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        for(int x = 1; x <= n; x++) { // 扫描n种可能性
            int first = binfind(nums,x); // 返回的是索引
            if(x == n - first) {
                return x;
            }
        }
        return -1;
    }
    // 定义二分，找到有序数组中第一个大于等于x的元素, 返回的是对应元素的索引
    public static int binfind(int[] nums,int x) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < x) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

}
